package com.study;

import java.util.Arrays;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-10-30 14:14
 * @version: 1.0
 * @description: 字符串搜索
 * 给定两个字符串A、B，判断B在A中是否存在，存在返回A的下标，不存在返回 -1
 **/
public class KPM {

    /*
        PMT: 前缀集合和后缀集合的交集中，最长元素的长度
        prefix: 每一个下标对应一个PMT值，组成数组
        next: prefix 向右移动一个下标 组成next数组
     */

    static void getNext(char[] pattern, int[] next){
        next[0] = -1;
        int j = 0,k = -1;

        while (j < pattern.length - 1){
            if (k == -1 || pattern[j] == pattern[k]){
                j++;
                k++;
                next[j] = k;
            }else {

                k = next[k];
            }
        }
    }

    static int search(char[] str,char[] pattern,int[] next){
        int i = 0, j = 0;
        while (i < str.length && j < pattern.length){ // 当j为 -1 时，要移动的是i，同时j也要归0
            if(j == -1 || str[i] == pattern[j]){
                i++;
                j++;
            }else {
                // i 不需要回溯 i = i - j + 1
                // j 回到指定位置
                j = next[j];
            }
        }

        if (j == pattern.length){
            return i - j;
        }
        return -1;
    }

    public static void main(String[] args) {
//        String a = "ashfbcdefadsaf";
//        String b = "adsa";
//        System.out.println(bf(a, b));
        String a = "ABCABCAABCABCD";
        String b = "ABCABCD";
        int[] next = new int[b.length()];
        getNext(b.toCharArray(),next);
        int search = search(a.toCharArray(), b.toCharArray(), next);
        System.out.println(Arrays.toString(next));
        System.out.println(search);
    }

    /**
     * boyer moore 从尾部开始匹配
     * @param ts
     * @param ps
     * @return
     */
    static int bm(String ts,String ps){
        return 0;
    }



    /**
     * 暴力搜索
     * @param ts 主字符串
     * @param ps 要查找的字符串
     * @return   找到就返回在主串中出现的第一个字符下标
     */
    static int bf(String ts,String ps){
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0, j = 0;

        while(i < t.length && j < p.length){
            if(t[i] == p[j]){
                i++;
                j++;
            }else {
                i = i - j + 1;
                j = 0;
            }
            if (j == p.length){
                return i - j;
            }
        }

        return -1;

    }

}
